{
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The greatest common divisor of 69 and 7 is 1, the inverse exists, which is 10\n"
          ]
        }
      ],
      "source": [
        "def extended_euclidean_algorithm(a, b):\n",
        "    x1, y1, x2, y2 = 1, 0, 0, 1\n",
        "    \n",
        "    while b:\n",
        "        q = a // b\n",
        "        a, b = b, a % b\n",
        "        x1, x2 = x2, x1 - q * x2\n",
        "        y1, y2 = y2, y1 - q * y2\n",
        "\n",
        "    return a, x1, y1\n",
        "\n",
        "# Example\n",
        "y = 7\n",
        "n = 69\n",
        "gcd_result, k, w = extended_euclidean_algorithm(n, y)\n",
        "if gcd_result == 1:\n",
        "    print(f'The greatest common divisor of {n} and {y} is {gcd_result}, the inverse exists, which is {w}')\n",
        "else:\n",
        "    print(f\"The greatest common divisor of {n} and {y} is {gcd_result}, the inverse doesn't exist\")\n",
        "\n",
        "# The greatest common divisor of 69 and 7 is 1, the inverse exists, which is 10"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "The greatest common divisor of 7 and 69 is 1, Modular Inverse exists, which is 10\n"
          ]
        }
      ],
      "source": [
        "def gcd(a, b):\n",
        "    if a < b :\n",
        "          a, b = b, a\n",
        "    while a % b != 0 :\n",
        "          a, b = b, a % b\n",
        "    return b\n",
        "\n",
        "def ext_gcd(a, b):\n",
        "    if b == 0:\n",
        "        return 1, 0\n",
        "    else:\n",
        "        x, y = ext_gcd(b, a%b)\n",
        "        x, y = y, x - (a//b) * y\n",
        "        return x, y\n",
        "\n",
        "def get_inverse(a, N):\n",
        "    if gcd(a, N) == 1:\n",
        "        x, y = ext_gcd(a, N)\n",
        "        return (x + N) % N\n",
        "    print(\"No inverse!\")\n",
        "    return 0\n",
        "\n",
        "a = 7\n",
        "N = 69\n",
        "print(f'The greatest common divisor of {a} and {N} is {gcd(a, N)}, the inverse exists, which is {get_inverse(a, N)}')"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "trusted": true
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "10\n"
          ]
        }
      ],
      "source": [
        "# Call third-party package to find modular multiplicative inverse\n",
        "from Crypto.Util.number import *\n",
        "print(inverse(7, 69))"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "trusted": true
      },
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python (Pyodide)",
      "language": "python",
      "name": "python"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "python",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}
